package com.tree;

/**
 * 路径压缩:
 * 压缩,就是把垂直的东西压扁,所以对于一个垂直的一个树,我们需要让他的层数减少
 * 方法很简单,如果想压缩 k 节点,就让 "k的父节点" 成为 "k的父节点的父节点" 就好
 * 即 unionArr[k] = unionArr[unionArr[k]]
 */
public class UnionFindImpl_5 extends UnionFindImpl_2 implements IUnionFind {

    @Override
    public int find(int p) {
        assert (p >= 0 && p < count);
        while (unionArr[p] != p) {
            /*增加下边这一步就好,这里不会有下标越界的问题,因为 unionArr[root] == unionArr[unionArr[root]]*/
            unionArr[p] = unionArr[unionArr[p]];
            p = unionArr[p];
        }
        return p;
    }

    /*这是一种最极端的路径压缩,将所有除根节点外的节点平铺,在执行这部操作后,find[p]只需要1步*/
    public int pathCompression(int p) {
        if (p != unionArr[p]) {
            //如果 p 的父节点 不等于 p,那么就一直递归的寻找 p 的根节点,到最后让 unionArr[p] = p的根节点
            unionArr[p] = pathCompression(unionArr[p]);
        }
        return unionArr[p];
    }

    public UnionFindImpl_5(int count) {
        super(count);
    }
}
